#include <stdio.h>
#include "LinkStack.h"
#include "LinkQueue.h"

// 两个栈实现一个队列

struct MyQueue
{
    LStack *s1;
    LStack *s2;
};
typedef struct MyQueue MQueue;

void InitMQueue(MQueue *q)
{
    q->s1 = InitLStack();
    q->s2 = InitLStack();
}

//入队列
void MyQPush(MQueue *q,ElementType element)
{
    //s2栈不为空时,把s2的数全部压到s1里去
    while(IsStackEmpty(q->s2) == false)
    {
        SPush(q->s1,*GetSTop(q->s2)) ;
        SPop(q->s2);
    }
    //正常向s1压数据
    SPush(q->s1,element);
}

//判断队列是否为空
bool IsMQueueEmpty(MQueue *q)
{
    //两个栈都为空队列即为空
    return IsStackEmpty(q->s1) && IsStackEmpty(q->s2);
}

//出队列
void MQPop(MQueue *q)
{
    //判断两个栈是否都是空
    if(IsMQueueEmpty(q) == true)
    {
        printf("队列为空!\n");
        return;
    }
    //数据全部在s1栈中
    while(IsStackEmpty(q->s1) == false)
    {
        SPush(q->s2,*GetSTop(q->s1));
        SPop(q->s1);
    }
    SPop(q->s2);
}

//获取队头元素
ElementType* GetMQueueTop(MQueue *q)
{
    //判断两个栈是否都是空
    if(IsMQueueEmpty(q) == true)
    {
        printf("队列为空!\n");
        return NULL;
    }
    //把数据全部导到s2里去
    while(IsStackEmpty(q->s1) == false)
    {
        SPush(q->s2,*GetSTop(q->s1));
        SPop(q->s1);
    }
    return GetSTop(q->s2);
}

//清理队列
void ClearMQueue(MQueue *q)
{
    //清理队列即清理内部的两个栈
    ClearLStack(q->s1,NULL);
    ClearLStack(q->s2,NULL);
}



// 两个队列实现一个栈
struct MyStack
{
    LQueue *q1;
    LQueue *q2;
    ElementType data;//存储栈顶元素
};
typedef struct MyStack MStack;

void InitMStack(MStack *s)
{
    s->q1 = InitLQueue();
    s->q2 = InitLQueue();
}

//入栈
void MSPush(MStack *s,ElementType element)
{
    if(IsQueueEmpty(s->q1) == true)
    {
        QPush(s->q2,element);
    }
    else
    {
        QPush(s->q1,element);
    }
}

//出栈 + 获取栈顶元素(返回指针而不是返回值,是为了判断栈为空的情况的返回值)
ElementType* MSPop(MStack *s)
{
    if(IsQueueEmpty(s->q1) == true && IsQueueEmpty(s->q2) == true)
    {
        printf("栈为空!\n");
        return NULL;
    }
    else if(IsQueueEmpty(s->q1) == true)
    {
        //把队列的数据放到另一个数据中,只剩一个,这一个就是栈顶元素
        while(GetQueueLen(s->q2) > 1)
        {
            //把q2的数据往q1里面塞,塞到只剩一个
            QPush(s->q1,*GetQFront(s->q2));
            //循环弹出队头的元素
            QPop(s->q2);
        }
        //获取栈顶元素(把栈顶元素放到一个生命周期更长的空间data里,防止指针变成野指针)
        s->data = *GetQFront(s->q2);
        //弹出栈顶元素
        QPop(s->q2);
    }
    else
    {
        while(GetQueueLen(s->q1) > 1)
        {
            //把q1的数据往q2里面塞,塞到只剩一个
            QPush(s->q2,*GetQFront(s->q1));
            //循环弹出队头的元素
            QPop(s->q1);
        }
        //获取栈顶元素
        s->data = *GetQFront(s->q1);
        //弹出栈顶元素
        QPop(s->q1);
    }
    return &s->data;
}

bool IsMStackEmpty(MStack *s)
{
    return IsQueueEmpty(s->q1) && IsQueueEmpty(s->q2);
}

void ClearMStack(MStack *s)
{
    ClearLQueue(s->q1,NULL);
    ClearLQueue(s->q2,NULL);
}






int main()
{
    MQueue q;
    InitMQueue(&q);
    for(long i = 1; i <= 10; i++)
    {
        MyQPush(&q,(void*)i);
    }
    while(IsMQueueEmpty(&q) == false)
    {
        printf("%ld ",(long)*GetMQueueTop(&q));
        MQPop(&q);
    }
    printf("\n");
    ClearMQueue(&q);

    MStack s;
    InitMStack(&s);
    for(long i = 1; i <= 10; i++)
    {
        MSPush(&s,(void*)i);
    }
    while(IsMStackEmpty(&s) == false)
    {
        printf("%ld ",(long)*MSPop(&s));
    }
    printf("\n");
    ClearMStack(&s);
    return 0;
}